#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

const int VMAX = 1000;

// The edge in the adjacency matrix.
struct Edge
{
	int v;		// The sink Edge of the edge.
	int cap;	// The capacity flow of the edge.
	int flow;	// The current flow in the edge.
	Edge *dup;	// The source Edge of the edge.
	Edge *next;	// The next edge in the adjacency matrix.

	Edge() {}
	Edge(int _v, int _cap, int _flow, Edge *_next)
	{
		v = _v; cap = _cap; flow = _flow; next = _next;
	}
};

Edge *graph[VMAX];
int h[VMAX], wt[VMAX];	// Height and excess flow of the Edge

// How much flow we can push into this edge.
#define Q(u) ((u)->cap < 0 ? -(u)->flow : (u)->cap - (u)->flow)
// Choose the smaller one between the maximum flow we can push
// and the excess flow.
inline int P(Edge *u, int v)
{
	return Q(u) > wt[v] ? wt[v] : Q(u);
}

void init_graph()
{
	memset(graph, 0, sizeof(graph));
}

void init_height(int s, int t, int n)
{
	int flag[VMAX];
	queue<int> q;

	memset(flag, 0, sizeof(flag[0]) * n);
	memset(h, 0, sizeof(h[0]) * n);

	h[t] = 0;
	flag[t] = 1;
	q.push(t);

	while(!q.empty())
	{
		int now = q.front();
		q.pop();

		for(Edge *p = graph[now];p;p = p->next)
		{
			if(!flag[p->v] && p->cap < 0)
			//if(!flag[p->v])
			{
				h[p->v] = h[now] + 1;
				flag[p->v] = 1;
				if(p->v != s)
					q.push(p->v);
			}
		}
	}

	// Set the height of the source to the largest one.
	for(int i = 0;i<n;i++)
		h[s] = max(h[i], h[s]);
	++h[s];
}

void init_wt(int s, int t, int n)
{
	memset(wt, 0, sizeof(wt[0]) * n);
	wt[s] = 1000000000;
	wt[t] = -wt[s];
}

void insert_edge(int s, int t, int cap, int flow = 0)
{
	graph[s] = new Edge(t, cap, flow, graph[s]);
	graph[t] = new Edge(s, -cap, -flow, graph[t]);
	graph[s]->dup = graph[t];
	graph[t]->dup = graph[s];
}

void preflow_push(int s, int t, int n)
{
	init_wt(s, t, n);
	init_height(s, t, n);

	queue<int> q;
	q.push(s);

	while(!q.empty())
	{
		int v = q.front();
		q.pop();

		for(Edge *u = graph[v];u;u = u->next)
		{
			if(P(u, v) > 0 && (v == s || h[v] == h[u->v] + 1))
			{
				int flow = P(u, v);
				u->flow += flow; u->dup->flow -= flow;
				wt[v] -= flow; wt[u->v] += flow;

				if(u->v != s && u->v != t)
					q.push(u->v);
			}
		}

		if(v != s && v != t && wt[v] > 0)
		{
			++h[v];
			q.push(v);
		}
	}
}

int max_flow(int s, int t, int n)
{
	preflow_push(s, t, n);

	int ret = 0;
	for(Edge *p = graph[s];p;p = p->next)
		ret += p->flow;

	return ret;
}

int matrix[VMAX][VMAX];

void floyed(int n)
{
	for(int k = 0;k<n;k++)
	{
		for(int i = 0;i<n;i++)
		{
			for(int j = 0;j<n;j++)
			{
				if(i^j && i^k && j^k)
				{
					matrix[i][j] = min(matrix[i][k] + matrix[k][j], matrix[i][j]);
				}
			}
		}
	}
}

int pass(int k, int c, int m, int len)
{
	init_graph();

	for(int i = 1;i<=k;i++)
	{
		//insert_edge(0, i, m);
		//cap[0][i] = m;
		insert_edge(0, i, m);
	}
	for(int i = 0;i<k;i++)
	{
		for(int j = k;j<k+c;j++)
		{
			if(matrix[i][j] <= len)
			{
				//cap[i+1][j+1] = 1;
				insert_edge(i+1, j+1, 1);
			}
		}
	}
	for(int i = k + 1;i<=k+c;i++)
	{
		insert_edge(i, k + c + 1, 1);

	}

	int ret =  max_flow(0, k + c + 1, k + c + 2) >= c;

	return ret;
}

int main()
{
	freopen("data.in", "r", stdin);
	int k, c, m;

	scanf("%d%d%d", &k, &c, &m);

	for(int i = 0;i<k + c;i++)
	{
		for(int j = 0;j<k + c;j++)
		{
			scanf("%d", &matrix[i][j]);
			if(!matrix[i][j] && i^j)
				matrix[i][j] = 1000000000;
		}
	}

	floyed(k + c);

	int low, high;

	low = 1;
	high = 2;

	while(!pass(k, c, m, high))
		high <<= 1;

	int mid;
	while(low < high)
	{
		mid = (low + high) >> 1;
		if(pass(k, c, m, mid))
			high = mid;
		else
			low = mid + 1;
	}

	printf("%d\n", low);

	return 0;
}
